#include<bits/stdc++.h>
using namespace std;

const int MOD = 32767;

long long pell(int n)
{
	if(n == 1)
		return 1;
	if(n == 2)
		return 2;
//	return (2*pell(n-1)%MOD+pell(n-2)%MOD)%MOD;
	long long f1 = 1, f2 = 2, f3;
	for(int i = 3;i <= n;i++)
	{
		f3 = (2*f2%MOD) + (f1%MOD);
		f1 = f2;
		f2 = f3%MOD;
	}
	return f3%MOD;
}

int main()
{
	int n, x;
	cin>>n;
	while(n--)
	{
		cin>>x;
		cout<<pell(x)<<endl;
	}
	return 0;
}

